#define _CRT_SECURE_NO_WARNINGS 1
//#include <cstddef>
//#include <cstdlib>
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        // write code here
//        ListNode* ghead, * gtail, * lhead, * ltail;
//        ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
//        lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
//        struct ListNode* cur = pHead;
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                ltail->next = cur;
//                ltail = ltail->next;
//            }
//            else
//            {
//                gtail->next = cur;
//                gtail = gtail->next;
//            }
//            cur = cur->next;
//        }
//        ltail->next = ghead->next;
//        gtail->next = NULL;
//        struct ListNode* head = lhead->next;
//        free(ghead);
//        free(lhead);
//        return head;
//    }
//};
